Search Results

Documents authored by de Wolf, Ronald

Document
DOI: 10.4230/LIPIcs.FSTTCS.2023.32
Tight Bounds for the Randomized and Quantum Communication Complexities of Equality with Small Error

Authors: Olivier Lalonde, Nikhil S. Mande, and Ronald de Wolf

Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

Abstract
We investigate the randomized and quantum communication complexities of the well-studied Equality function with small error probability ε, getting the optimal constant factors in the leading terms in various different models. The following are our results in the randomized model: - We give a general technique to convert public-coin protocols to private-coin protocols by incurring a small multiplicative error at a small additive cost. This is an improvement over Newman’s theorem [Inf. Proc. Let.'91] in the dependence on the error parameter. - As a consequence we obtain a (log(n/ε²) + 4)-cost private-coin communication protocol that computes the n-bit Equality function, to error ε. This improves upon the log(n/ε³) + O(1) upper bound implied by Newman’s theorem, and matches the best known lower bound, which follows from Alon [Comb. Prob. Comput.'09], up to an additive log log(1/ε) + O(1). The following are our results in various quantum models: - We exhibit a one-way protocol with log(n/ε) + 4 qubits of communication for the n-bit Equality function, to error ε, that uses only pure states. This bound was implicitly already shown by Nayak [PhD thesis'99]. - We give a near-matching lower bound: any ε-error one-way protocol for n-bit Equality that uses only pure states communicates at least log(n/ε) - log log(1/ε) - O(1) qubits. - We exhibit a one-way protocol with log(√n/ε) + 3 qubits of communication that uses mixed states. This is tight up to additive log log(1/ε) + O(1), which follows from Alon’s result. - We exhibit a one-way entanglement-assisted protocol achieving error probability ε with ⌈log(1/ε)⌉ + 1 classical bits of communication and ⌈log(√n/ε)⌉ + 4 shared EPR-pairs between Alice and Bob. This matches the communication cost of the classical public coin protocol achieving the same error probability while improving upon the amount of prior entanglement that is needed for this protocol, which is ⌈log(n/ε)⌉ + O(1) shared EPR-pairs. Our upper bounds also yield upper bounds on the approximate rank, approximate nonnegative-rank, and approximate psd-rank of the Identity matrix. As a consequence we also obtain improved upper bounds on these measures for a function that was recently used to refute the randomized and quantum versions of the log-rank conjecture (Chattopadhyay, Mande and Sherif [J. ACM'20], Sinha and de Wolf [FOCS'19], Anshu, Boddu and Touchette [FOCS'19]).
Cite as

Olivier Lalonde, Nikhil S. Mande, and Ronald de Wolf. Tight Bounds for the Randomized and Quantum Communication Complexities of Equality with Small Error. In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 32:1-32:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{lalonde_et_al:LIPIcs.FSTTCS.2023.32,
  author =	{Lalonde, Olivier and Mande, Nikhil S. and de Wolf, Ronald},
  title =	{{Tight Bounds for the Randomized and Quantum Communication Complexities of Equality with Small Error}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{32:1--32:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-304-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{284},
  editor =	{Bouyer, Patricia and Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.32},
  URN =		{urn:nbn:de:0030-drops-194055},
  doi =		{10.4230/LIPIcs.FSTTCS.2023.32},
  annote =	{Keywords: Communication complexity, quantum communication complexity}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.64
Improved Quantum Boosting

Authors: Adam Izdebski and Ronald de Wolf

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
Boosting is a general method to convert a weak learner (which generates hypotheses that are just slightly better than random) into a strong learner (which generates hypotheses that are much better than random). Recently, Arunachalam and Maity [Srinivasan Arunachalam and Reevu Maity, 2020] gave the first quantum improvement for boosting, by combining Freund and Schapire’s AdaBoost algorithm with a quantum algorithm for approximate counting. Their booster is faster than classical boosting as a function of the VC-dimension of the weak learner’s hypothesis class, but worse as a function of the quality of the weak learner. In this paper we give a substantially faster and simpler quantum boosting algorithm, based on Servedio’s SmoothBoost algorithm [Servedio, 2003].
Cite as

Adam Izdebski and Ronald de Wolf. Improved Quantum Boosting. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 64:1-64:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{izdebski_et_al:LIPIcs.ESA.2023.64,
  author =	{Izdebski, Adam and de Wolf, Ronald},
  title =	{{Improved Quantum Boosting}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{64:1--64:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.64},
  URN =		{urn:nbn:de:0030-drops-187178},
  doi =		{10.4230/LIPIcs.ESA.2023.64},
  annote =	{Keywords: Learning theory, Boosting algorithms, Quantum computing}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.81
Tight Bounds for Quantum Phase Estimation and Related Problems

Authors: Nikhil S. Mande and Ronald de Wolf

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
Phase estimation, due to Kitaev [arXiv'95], is one of the most fundamental subroutines in quantum computing, used in Shor’s factoring algorithm, optimization algorithms, quantum chemistry algorithms, and many others. In the basic scenario, one is given black-box access to a unitary U, and an eigenstate |ψ⟩ of U with unknown eigenvalue e^{iθ}, and the task is to estimate the eigenphase θ within ±δ, with high probability. The repeated application of U and U^{-1} is typically the most expensive part of phase estimation, so for us the cost of an algorithm will be that number of applications. Motivated by the "guided Hamiltonian problem" in quantum chemistry, we tightly characterize the cost of several variants of phase estimation where we are no longer given an arbitrary eigenstate, but are required to estimate the maximum eigenphase of U, aided by advice in the form of states (or a unitary preparing those states) which are promised to have at least a certain overlap γ with the top eigenspace. We give algorithms and matching lower bounds (up to logarithmic factors) for all ranges of parameters. We show a crossover point below which advice is not helpful: o(1/γ²) copies of the advice state (or o(1/γ) applications of an advice-preparing unitary) are not significantly better than having no advice at all. We also show that having knowledge of the eigenbasis of U does not significantly reduce cost. Our upper bounds use the subroutine of generalized maximum-finding of van Apeldoorn, Gilyén, Gribling, and de Wolf [Quantum'20], the state-based Hamiltonian simulation of Lloyd, Mohseni, and Rebentrost [Nature Physics'13], and several other techniques. Our lower bounds follow by reductions from a fractional version of the Boolean OR function with advice, which we lower bound by a simple modification of the adversary method of Ambainis [JCSS'02]. As an immediate consequence we also obtain a lower bound on the complexity of the Unitary recurrence time problem, matching an upper bound of She and Yuen [ITCS'23] and resolving an open question posed by them. Lastly, we study how efficiently one can reduce the error probability in the basic phase-estimation scenario. We show that an algorithm solving phase estimation to precision δ with error probability at most ε must have cost Ω(1/δ log(1/ε)), matching the obvious way to error-reduce the basic constant-error-probability phase estimation algorithm. This contrasts with some other scenarios in quantum computing (e.g. search) where error-reduction costs only a factor O(√{log(1/ε)}). Our lower bound technique uses a variant of the polynomial method with trigonometric polynomials.
Cite as

Nikhil S. Mande and Ronald de Wolf. Tight Bounds for Quantum Phase Estimation and Related Problems. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 81:1-81:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{mande_et_al:LIPIcs.ESA.2023.81,
  author =	{Mande, Nikhil S. and de Wolf, Ronald},
  title =	{{Tight Bounds for Quantum Phase Estimation and Related Problems}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{81:1--81:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.81},
  URN =		{urn:nbn:de:0030-drops-187346},
  doi =		{10.4230/LIPIcs.ESA.2023.81},
  annote =	{Keywords: Phase estimation, quantum computing}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.38
Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints

Authors: Yanlin Chen and Ronald de Wolf

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
Lasso and Ridge are important minimization problems in machine learning and statistics. They are versions of linear regression with squared loss where the vector θ ∈ ℝ^d of coefficients is constrained in either 𝓁₁-norm (for Lasso) or in 𝓁₂-norm (for Ridge). We study the complexity of quantum algorithms for finding ε-minimizers for these minimization problems. We show that for Lasso we can get a quadratic quantum speedup in terms of d by speeding up the cost-per-iteration of the Frank-Wolfe algorithm, while for Ridge the best quantum algorithms are linear in d, as are the best classical algorithms. As a byproduct of our quantum lower bound for Lasso, we also prove the first classical lower bound for Lasso that is tight up to polylog-factors.
Cite as

Yanlin Chen and Ronald de Wolf. Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 38:1-38:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ICALP.2023.38,
  author =	{Chen, Yanlin and de Wolf, Ronald},
  title =	{{Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{38:1--38:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.38},
  URN =		{urn:nbn:de:0030-drops-180907},
  doi =		{10.4230/LIPIcs.ICALP.2023.38},
  annote =	{Keywords: Quantum algorithms, Regularized linear regression, Lasso, Ridge, Lower bounds}
}
Document
DOI: 10.4230/LIPIcs.CCC.2022.28
Influence in Completely Bounded Block-Multilinear Forms and Classical Simulation of Quantum Algorithms

Authors: Nikhil Bansal, Makrand Sinha, and Ronald de Wolf

Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)

Abstract
The Aaronson-Ambainis conjecture (Theory of Computing '14) says that every low-degree bounded polynomial on the Boolean hypercube has an influential variable. This conjecture, if true, would imply that the acceptance probability of every d-query quantum algorithm can be well-approximated almost everywhere (i.e., on almost all inputs) by a poly(d)-query classical algorithm. We prove a special case of the conjecture: in every completely bounded degree-d block-multilinear form with constant variance, there always exists a variable with influence at least 1/poly(d). In a certain sense, such polynomials characterize the acceptance probability of quantum query algorithms, as shown by Arunachalam, Briët and Palazuelos (SICOMP '19). As a corollary we obtain efficient classical almost-everywhere simulation for a particular class of quantum algorithms that includes for instance k-fold Forrelation. Our main technical result relies on connections to free probability theory.
Cite as

Nikhil Bansal, Makrand Sinha, and Ronald de Wolf. Influence in Completely Bounded Block-Multilinear Forms and Classical Simulation of Quantum Algorithms. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 28:1-28:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bansal_et_al:LIPIcs.CCC.2022.28,
  author =	{Bansal, Nikhil and Sinha, Makrand and de Wolf, Ronald},
  title =	{{Influence in Completely Bounded Block-Multilinear Forms and Classical Simulation of Quantum Algorithms}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{28:1--28:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-241-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{234},
  editor =	{Lovett, Shachar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.28},
  URN =		{urn:nbn:de:0030-drops-165908},
  doi =		{10.4230/LIPIcs.CCC.2022.28},
  annote =	{Keywords: Aaronson-Ambainis conjecture, Quantum query complexity, Classical query complexity, Free probability, Completely bounded norm, Analysis of Boolean functions, Influence}
}
Document
DOI: 10.4230/LIPIcs.STACS.2022.20
Symmetry and Quantum Query-To-Communication Simulation

Authors: Sourav Chakraborty, Arkadev Chattopadhyay, Peter Høyer, Nikhil S. Mande, Manaswi Paraashar, and Ronald de Wolf

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
Buhrman, Cleve and Wigderson (STOC'98) showed that for every Boolean function f : {-1,1}ⁿ → {-1,1} and G ∈ {AND₂, XOR₂}, the bounded-error quantum communication complexity of the composed function f∘G equals O(𝖰(f) log n), where 𝖰(f) denotes the bounded-error quantum query complexity of f. This is achieved by Alice running the optimal quantum query algorithm for f, using a round of O(log n) qubits of communication to implement each query. This is in contrast with the classical setting, where it is easy to show that 𝖱^{cc}(f∘G) ≤ 2𝖱(f), where 𝖱^{cc} and 𝖱 denote bounded-error communication and query complexity, respectively. Chakraborty et al. (CCC'20) exhibited a total function for which the log n overhead in the BCW simulation is required. This established the somewhat surprising fact that quantum reductions are in some cases inherently more expensive than classical reductions. We improve upon their result in several ways. - We show that the log n overhead is not required when f is symmetric (i.e., depends only on the Hamming weight of its input), generalizing a result of Aaronson and Ambainis for the Set-Disjointness function (Theory of Computing'05). Our upper bound assumes a shared entangled state, though for most symmetric functions the assumed number of entangled qubits is less than the communication and hence could be part of the communication. - In order to prove the above, we design an efficient distributed version of noisy amplitude amplification that allows us to prove the result when f is the OR function. This also provides a different, and arguably simpler, proof of Aaronson and Ambainis’s O(√n) communication upper bound for Set-Disjointness. - In view of our first result above, one may ask whether the log n overhead in the BCW simulation can be avoided even when f is transitive, which is a weaker notion of symmetry. We give a strong negative answer by showing that the log n overhead is still necessary for some transitive functions even when we allow the quantum communication protocol an error probability that can be arbitrarily close to 1/2 (this corresponds to the unbounded-error model of communication). - We also give, among other things, a general recipe to construct functions for which the log n overhead is required in the BCW simulation in the bounded-error communication model, even if the parties are allowed to share an arbitrary prior entangled state for free.
Cite as

Sourav Chakraborty, Arkadev Chattopadhyay, Peter Høyer, Nikhil S. Mande, Manaswi Paraashar, and Ronald de Wolf. Symmetry and Quantum Query-To-Communication Simulation. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 20:1-20:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.STACS.2022.20,
  author =	{Chakraborty, Sourav and Chattopadhyay, Arkadev and H{\o}yer, Peter and Mande, Nikhil S. and Paraashar, Manaswi and de Wolf, Ronald},
  title =	{{Symmetry and Quantum Query-To-Communication Simulation}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{20:1--20:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.20},
  URN =		{urn:nbn:de:0030-drops-158309},
  doi =		{10.4230/LIPIcs.STACS.2022.20},
  annote =	{Keywords: Classical and quantum communication complexity, query-to-communication-simulation, quantum computing}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.110
Quantum Algorithms for Matrix Scaling and Matrix Balancing

Authors: Joran van Apeldoorn, Sander Gribling, Yinan Li, Harold Nieuwboer, Michael Walter, and Ronald de Wolf

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
Matrix scaling and matrix balancing are two basic linear-algebraic problems with a wide variety of applications, such as approximating the permanent, and pre-conditioning linear systems to make them more numerically stable. We study the power and limitations of quantum algorithms for these problems. We provide quantum implementations of two classical (in both senses of the word) methods: Sinkhorn’s algorithm for matrix scaling and Osborne’s algorithm for matrix balancing. Using amplitude estimation as our main tool, our quantum implementations both run in time Õ(√{mn}/ε⁴) for scaling or balancing an n × n matrix (given by an oracle) with m non-zero entries to within 𝓁₁-error ε. Their classical analogs use time Õ(m/ε²), and every classical algorithm for scaling or balancing with small constant ε requires Ω(m) queries to the entries of the input matrix. We thus achieve a polynomial speed-up in terms of n, at the expense of a worse polynomial dependence on the obtained 𝓁₁-error ε. Even for constant ε these problems are already non-trivial (and relevant in applications). Along the way, we extend the classical analysis of Sinkhorn’s and Osborne’s algorithm to allow for errors in the computation of marginals. We also adapt an improved analysis of Sinkhorn’s algorithm for entrywise-positive matrices to the 𝓁₁-setting, obtaining an Õ(n^{1.5}/ε³)-time quantum algorithm for ε-𝓁₁-scaling. We also prove a lower bound, showing our quantum algorithm for matrix scaling is essentially optimal for constant ε: every quantum algorithm for matrix scaling that achieves a constant 𝓁₁-error w.r.t. uniform marginals needs Ω(√{mn}) queries.
Cite as

Joran van Apeldoorn, Sander Gribling, Yinan Li, Harold Nieuwboer, Michael Walter, and Ronald de Wolf. Quantum Algorithms for Matrix Scaling and Matrix Balancing. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 110:1-110:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{vanapeldoorn_et_al:LIPIcs.ICALP.2021.110,
  author =	{van Apeldoorn, Joran and Gribling, Sander and Li, Yinan and Nieuwboer, Harold and Walter, Michael and de Wolf, Ronald},
  title =	{{Quantum Algorithms for Matrix Scaling and Matrix Balancing}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{110:1--110:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.110},
  URN =		{urn:nbn:de:0030-drops-141793},
  doi =		{10.4230/LIPIcs.ICALP.2021.110},
  annote =	{Keywords: Matrix scaling, matrix balancing, quantum algorithms}
}
Document
DOI: 10.4230/LIPIcs.TQC.2020.10
Quantum Coupon Collector

Authors: Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis, and Ronald de Wolf

Published in: LIPIcs, Volume 158, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)

Abstract
We study how efficiently a k-element set S⊆[n] can be learned from a uniform superposition |S> of its elements. One can think of |S>=∑_{i∈S}|i>/√|S| as the quantum version of a uniformly random sample over S, as in the classical analysis of the "coupon collector problem." We show that if k is close to n, then we can learn S using asymptotically fewer quantum samples than random samples. In particular, if there are n-k=O(1) missing elements then O(k) copies of |S> suffice, in contrast to the Θ(k log k) random samples needed by a classical coupon collector. On the other hand, if n-k=Ω(k), then Ω(k log k) quantum samples are necessary. More generally, we give tight bounds on the number of quantum samples needed for every k and n, and we give efficient quantum learning algorithms. We also give tight bounds in the model where we can additionally reflect through |S>. Finally, we relate coupon collection to a known example separating proper and improper PAC learning that turns out to show no separation in the quantum case.
Cite as

Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis, and Ronald de Wolf. Quantum Coupon Collector. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 158, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{arunachalam_et_al:LIPIcs.TQC.2020.10,
  author =	{Arunachalam, Srinivasan and Belovs, Aleksandrs and Childs, Andrew M. and Kothari, Robin and Rosmanis, Ansis and de Wolf, Ronald},
  title =	{{Quantum Coupon Collector}},
  booktitle =	{15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)},
  pages =	{10:1--10:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-146-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{158},
  editor =	{Flammia, Steven T.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2020.10},
  URN =		{urn:nbn:de:0030-drops-120692},
  doi =		{10.4230/LIPIcs.TQC.2020.10},
  annote =	{Keywords: Quantum algorithms, Adversary method, Coupon collector, Quantum learning theory}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.45
Improved Bounds on Fourier Entropy and Min-Entropy

Authors: Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký, Nitin Saurabh, and Ronald de Wolf

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
Given a Boolean function f:{-1,1}ⁿ→ {-1,1}, define the Fourier distribution to be the distribution on subsets of [n], where each S ⊆ [n] is sampled with probability f̂(S)². The Fourier Entropy-Influence (FEI) conjecture of Friedgut and Kalai [E. Friedgut and G. Kalai, 1996] seeks to relate two fundamental measures associated with the Fourier distribution: does there exist a universal constant C>0 such that ℍ(f̂²)≤ C⋅ Inf(f), where ℍ(f̂²) is the Shannon entropy of the Fourier distribution of f and Inf(f) is the total influence of f? In this paper we present three new contributions towards the FEI conjecture: ii) Our first contribution shows that ℍ(f̂²) ≤ 2⋅ aUC^⊕(f), where aUC^⊕(f) is the average unambiguous parity-certificate complexity of f. This improves upon several bounds shown by Chakraborty et al. [S. Chakraborty et al., 2016]. We further improve this bound for unambiguous DNFs. iii) We next consider the weaker Fourier Min-entropy-Influence (FMEI) conjecture posed by O'Donnell and others [R. O'Donnell et al., 2011; R. O'Donnell, 2014] which asks if ℍ_{∞}(f̂²) ≤ C⋅ Inf(f), where ℍ_{∞}(f̂²) is the min-entropy of the Fourier distribution. We show ℍ_{∞}(f̂²) ≤ 2⋅?_{min}^⊕(f), where ?_{min}^⊕(f) is the minimum parity certificate complexity of f. We also show that for all ε ≥ 0, we have ℍ_{∞}(f̂²) ≤ 2log (‖f̂‖_{1,ε}/(1-ε)), where ‖f̂‖_{1,ε} is the approximate spectral norm of f. As a corollary, we verify the FMEI conjecture for the class of read-k DNFs (for constant k). iv) Our third contribution is to better understand implications of the FEI conjecture for the structure of polynomials that 1/3-approximate a Boolean function on the Boolean cube. We pose a conjecture: no flat polynomial (whose non-zero Fourier coefficients have the same magnitude) of degree d and sparsity 2^ω(d) can 1/3-approximate a Boolean function. This conjecture is known to be true assuming FEI and we prove the conjecture unconditionally (i.e., without assuming the FEI conjecture) for a class of polynomials. We discuss an intriguing connection between our conjecture and the constant for the Bohnenblust-Hille inequality, which has been extensively studied in functional analysis.
Cite as

Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký, Nitin Saurabh, and Ronald de Wolf. Improved Bounds on Fourier Entropy and Min-Entropy. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 45:1-45:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{arunachalam_et_al:LIPIcs.STACS.2020.45,
  author =	{Arunachalam, Srinivasan and Chakraborty, Sourav and Kouck\'{y}, Michal and Saurabh, Nitin and de Wolf, Ronald},
  title =	{{Improved Bounds on Fourier Entropy and Min-Entropy}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{45:1--45:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.45},
  URN =		{urn:nbn:de:0030-drops-119062},
  doi =		{10.4230/LIPIcs.STACS.2020.45},
  annote =	{Keywords: Fourier analysis of Boolean functions, FEI conjecture, query complexity, polynomial approximation, approximate degree, certificate complexity}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.16
Two New Results About Quantum Exact Learning

Authors: Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee, Manaswi Paraashar, and Ronald de Wolf

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
We present two new results about exact learning by quantum computers. First, we show how to exactly learn a k-Fourier-sparse n-bit Boolean function from O(k^{1.5}(log k)^2) uniform quantum examples for that function. This improves over the bound of Theta~(kn) uniformly random classical examples (Haviv and Regev, CCC'15). Our main tool is an improvement of Chang’s lemma for sparse Boolean functions. Second, we show that if a concept class {C} can be exactly learned using Q quantum membership queries, then it can also be learned using O ({Q^2}/{log Q} * log|C|) classical membership queries. This improves the previous-best simulation result (Servedio-Gortler, SICOMP'04) by a log Q-factor.
Cite as

Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee, Manaswi Paraashar, and Ronald de Wolf. Two New Results About Quantum Exact Learning. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{arunachalam_et_al:LIPIcs.ICALP.2019.16,
  author =	{Arunachalam, Srinivasan and Chakraborty, Sourav and Lee, Troy and Paraashar, Manaswi and de Wolf, Ronald},
  title =	{{Two New Results About Quantum Exact Learning}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{16:1--16:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.16},
  URN =		{urn:nbn:de:0030-drops-105929},
  doi =		{10.4230/LIPIcs.ICALP.2019.16},
  annote =	{Keywords: quantum computing, exact learning, analysis of Boolean functions, Fourier sparse Boolean functions}
}
Document
DOI: 10.4230/LIPIcs.CCC.2017.25
Optimal Quantum Sample Complexity of Learning Algorithms

Authors: Srinivasan Arunachalam and Ronald de Wolf

Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)

Abstract
In learning theory, the VC dimension of a concept class C is the most common way to measure its "richness". A fundamental result says that the number of examples needed to learn an unknown target concept c in C under an unknown distribution D, is tightly determined by the VC dimension d of the concept class C. Specifically, in the PAC model Theta(d/eps + log(1/delta)/eps) examples are necessary and sufficient for a learner to output, with probability 1-delta, a hypothesis h that is eps-close to the target concept c (measured under D). In the related agnostic model, where the samples need not come from a c in C, we know that Theta(d/eps^2 + log(1/delta)/eps^2) examples are necessary and sufficient to output an hypothesis h in C whose error is at most eps worse than the error of the best concept in C. Here we analyze quantum sample complexity, where each example is a coherent quantum state. This model was introduced by Bshouty and Jackson, who showed that quantum examples are more powerful than classical examples in some fixed-distribution settings. However, Atici and Servedio, improved by Zhang, showed that in the PAC setting (where the learner has to succeed for every distribution), quantum examples cannot be much more powerful: the required number of quantum examples is Omega(d^{1-eta}/eps + d + log(1/delta)/eps) for arbitrarily small constant eta>0. Our main result is that quantum and classical sample complexity are in fact equal up to constant factors in both the PAC and agnostic models. We give two proof approaches. The first is a fairly simple information-theoretic argument that yields the above two classical bounds and yields the same bounds for quantum sample complexity up to a log(d/eps) factor. We then give a second approach that avoids the log-factor loss, based on analyzing the behavior of the "Pretty Good Measurement" on the quantum state identification problems that correspond to learning. This shows classical and quantum sample complexity are equal up to constant factors for every concept class C.
Cite as

Srinivasan Arunachalam and Ronald de Wolf. Optimal Quantum Sample Complexity of Learning Algorithms. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 25:1-25:31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{arunachalam_et_al:LIPIcs.CCC.2017.25,
  author =	{Arunachalam, Srinivasan and de Wolf, Ronald},
  title =	{{Optimal Quantum Sample Complexity of Learning Algorithms}},
  booktitle =	{32nd Computational Complexity Conference (CCC 2017)},
  pages =	{25:1--25:31},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-040-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{79},
  editor =	{O'Donnell, Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.25},
  URN =		{urn:nbn:de:0030-drops-75241},
  doi =		{10.4230/LIPIcs.CCC.2017.25},
  annote =	{Keywords: Quantum computing, PAC learning, agnostic learning, VC dimension}
}
Document
DOI: 10.4230/LIPIcs.CCC.2016.17
On the Sum-of-Squares Degree of Symmetric Quadratic Functions

Authors: Troy Lee, Anupam Prakash, Ronald de Wolf, and Henry Yuen

Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)

Abstract
We study how well functions over the boolean hypercube of the form f_k(x)=(|x|-k)(|x|-k-1) can be approximated by sums of squares of low-degree polynomials, obtaining good bounds for the case of approximation in l_{infinity}-norm as well as in l_1-norm. We describe three complexity-theoretic applications: (1) a proof that the recent breakthrough lower bound of Lee, Raghavendra, and Steurer [Lee/Raghavendra/Steurer, STOC 2015] on the positive semidefinite extension complexity of the correlation and TSP polytopes cannot be improved further by showing better sum-of-squares degree lower bounds on l_1-approximation of f_k; (2) a proof that Grigoriev's lower bound on the degree of Positivstellensatz refutations for the knapsack problem is optimal, answering an open question from [Grigoriev, Comp. Compl. 2001]; (3) bounds on the query complexity of quantum algorithms whose expected output approximates such functions.
Cite as

Troy Lee, Anupam Prakash, Ronald de Wolf, and Henry Yuen. On the Sum-of-Squares Degree of Symmetric Quadratic Functions. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 17:1-17:31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{lee_et_al:LIPIcs.CCC.2016.17,
  author =	{Lee, Troy and Prakash, Anupam and de Wolf, Ronald and Yuen, Henry},
  title =	{{On the Sum-of-Squares Degree of Symmetric Quadratic Functions}},
  booktitle =	{31st Conference on Computational Complexity (CCC 2016)},
  pages =	{17:1--17:31},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-008-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{50},
  editor =	{Raz, Ran},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.17},
  URN =		{urn:nbn:de:0030-drops-58383},
  doi =		{10.4230/LIPIcs.CCC.2016.17},
  annote =	{Keywords: Sum-of-squares degree, approximation theory, Positivstellensatz refutations of knapsack, quantum query complexity in expectation, extension complexity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2013.424
Fooling One-Sided Quantum Protocols

Authors: Hartmut Klauck and Ronald de Wolf

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
We use the venerable "fooling set" method to prove new lower bounds on the quantum communication complexity of various functions. Let f : X x Y -> {0,1} be a Boolean function, fool^1(f) its maximal fooling set size among 1-inputs, Q_1^*(f) its one-sided-error quantum communication complexity with prior entanglement, and NQ(f) its nondeterministic quantum communication complexity (without prior entanglement; this model is trivial with shared randomness or entanglement). Our main results are the following, where logs are to base 2: - If the maximal fooling set is "upper triangular" (which is for instance the case for the equality, disjointness, and greater-than functions), then we have Q_1^*(f) >= 1/2 log fool^1(f) - 1/2, which (by superdense coding) is essentially optimal for functions like equality, disjointness, and greater-than. No super-constant lower bound for equality seems to follow from earlier techniques. - For all f we have Q_1^*(f) >= 1/4 log fool^1(f) - 1/2. - NQ(f) >= 1/2 log fool^1(f) + 1. We do not know if the factor 1/2 is needed in this result, but it cannot be replaced by 1: we give an example where NQ(f) \approx 0.613 log fool^1(f).
Cite as

Hartmut Klauck and Ronald de Wolf. Fooling One-Sided Quantum Protocols. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 424-433, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{klauck_et_al:LIPIcs.STACS.2013.424,
  author =	{Klauck, Hartmut and de Wolf, Ronald},
  title =	{{Fooling One-Sided Quantum Protocols}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{424--433},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.424},
  URN =		{urn:nbn:de:0030-drops-39539},
  doi =		{10.4230/LIPIcs.STACS.2013.424},
  annote =	{Keywords: Quantum computing, communication complexity, fooling set, lower bound}
}
Document
DOI: 10.4230/LIPIcs.STACS.2013.446
Optimal quantum query bounds for almost all Boolean functions

Authors: Andris Ambainis, Arturs Backurs, Juris Smotrovs, and Ronald de Wolf

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
We show that almost all n-bit Boolean functions have bounded-error quantum query complexity at least n/2, up to lower-order terms. This improves over an earlier n/4 lower bound of Ambainis (A. Ambainis, 1999), and shows that van Dam's oracle interrogation (W. van Dam, 1998) is essentially optimal for almost all functions. Our proof uses the fact that the acceptance probability of a T-query algorithm can be written as the sum of squares of degree-T polynomials.
Cite as

Andris Ambainis, Arturs Backurs, Juris Smotrovs, and Ronald de Wolf. Optimal quantum query bounds for almost all Boolean functions. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 446-453, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{ambainis_et_al:LIPIcs.STACS.2013.446,
  author =	{Ambainis, Andris and Backurs, Arturs and Smotrovs, Juris and de Wolf, Ronald},
  title =	{{Optimal quantum query bounds for almost all Boolean functions}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{446--453},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.446},
  URN =		{urn:nbn:de:0030-drops-39557},
  doi =		{10.4230/LIPIcs.STACS.2013.446},
  annote =	{Keywords: Quantum computing, query complexity, lower bounds, polynomial method}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2012.148
New bounds on the classical and quantum communication complexity of some graph properties

Authors: Gábor Ivanyos, Hartmut Klauck, Troy Lee, Miklos Santha, and Ronald de Wolf

Published in: LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)

Abstract
We study the communication complexity of a number of graph properties where the edges of the graph G are distributed between Alice and Bob (i.e., each receives some of the edges as input). Our main results are: 1. An Omega(n) lower bound on the quantum communication complexity of deciding whether an n-vertex graph G is connected, nearly matching the trivial classical upper bound of O(n log n) bits of communication. 2. A deterministic upper bound of O(n^{3/2} log n) bits for deciding if a bipartite graph contains a perfect matching, and a quantum lower bound of Omega(n) for this problem. 3. A Theta(n^2) bound for the randomized communication complexity of deciding if a graph has an Eulerian tour, and a Theta(n^{3/2}) bound for its quantum communication complexity. 4. The first two quantum lower bounds are obtained by exhibiting a reduction from the n-bit Inner Product problem to these graph problems, which solves an open question of Babai, Frankl and Simon [Babai et al 1986]. The third quantum lower bound comes from recent results about the quantum communication complexity of composed functions. We also obtain essentially tight bounds for the quantum communication complexity of a few other problems, such as deciding if $G$ is triangle-free, or if G is bipartite, as well as computing the determinant of a distributed matrix.
Cite as

Gábor Ivanyos, Hartmut Klauck, Troy Lee, Miklos Santha, and Ronald de Wolf. New bounds on the classical and quantum communication complexity of some graph properties. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 148-159, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{ivanyos_et_al:LIPIcs.FSTTCS.2012.148,
  author =	{Ivanyos, G\'{a}bor and Klauck, Hartmut and Lee, Troy and Santha, Miklos and de Wolf, Ronald},
  title =	{{New bounds on the classical and quantum communication complexity of some graph properties}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)},
  pages =	{148--159},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-47-7},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{18},
  editor =	{D'Souza, Deepak and Radhakrishnan, Jaikumar and Telikepalli, Kavitha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.148},
  URN =		{urn:nbn:de:0030-drops-38523},
  doi =		{10.4230/LIPIcs.FSTTCS.2012.148},
  annote =	{Keywords: Graph properties, communication complexity, quantum communication}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2010.145
New Results on Quantum Property Testing

Authors: Sourav Chakraborty, Eldar Fischer, Arie Matsliah, and Ronald de Wolf

Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)

Abstract
We present several new examples of speed-ups obtainable by quantum algorithms in the context of property testing. First, motivated by sampling algorithms, we consider probability distributions given in the form of an oracle $f:[n]\to[m]$. Here the probability $P_f(j)$ of an outcome $j$ in $[m]$ is the fraction of its domain that $f$ maps to $j$. We give quantum algorithms for testing whether two such distributions are identical or $epsilon$-far in $L_1$-norm. Recently, Bravyi, Hassidim, and Harrow showed that if $P_f$ and $P_g$ are both unknown (i.e., given by oracles $f$ and $g$), then this testing can be done in roughly $sqrt{m}$ quantum queries to the functions. We consider the case where the second distribution is known, and show that testing can be done with roughly $m^{1/3}$ quantum queries, which we prove to be essentially optimal. In contrast, it is known that classical testing algorithms need about $m^{2/3}$ queries in the unknown-unknown case and about $sqrt{m}$ queries in the known-unknown case. Based on this result, we also reduce the query complexity of graph isomorphism testers with quantum oracle access. While those examples provide polynomial quantum speed-ups, our third example gives a much larger improvement (constant quantum queries vs polynomial classical queries) for the problem of testing periodicity, based on Shor's algorithm and a modification of a classical lower bound by Lachish and Newman. This provides an alternative to a recent constant-vs-polynomial speed-up due to Aaronson.
Cite as

Sourav Chakraborty, Eldar Fischer, Arie Matsliah, and Ronald de Wolf. New Results on Quantum Property Testing. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 145-156, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.FSTTCS.2010.145,
  author =	{Chakraborty, Sourav and Fischer, Eldar and Matsliah, Arie and de Wolf, Ronald},
  title =	{{New Results on Quantum Property Testing}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)},
  pages =	{145--156},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-23-1},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{8},
  editor =	{Lodaya, Kamal and Mahajan, Meena},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.145},
  URN =		{urn:nbn:de:0030-drops-28603},
  doi =		{10.4230/LIPIcs.FSTTCS.2010.145},
  annote =	{Keywords: quantum algorithm, property testing}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2455
Efficient and Error-Correcting Data Structures for Membership and Polynomial Evaluation

Authors: Victor Chen, Elena Grigorescu, and Ronald de Wolf

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
We construct efficient data structures that are resilient against a constant fraction of adversarial noise. Our model requires that the decoder answers \emph{most} queries correctly with high probability and for the remaining queries, the decoder with high probability either answers correctly or declares ``don't know.'' Furthermore, if there is no noise on the data structure, it answers \emph{all} queries correctly with high probability. Our model is the common generalization of an error-correcting data structure model proposed recently by de~Wolf, and the notion of ``relaxed locally decodable codes'' developed in the PCP literature. We measure the efficiency of a data structure in terms of its \emph{length} (the number of bits in its representation), and query-answering time, measured by the number of \emph{bit-probes} to the (possibly corrupted) representation. We obtain results for the following two data structure problems: \begin{itemize} \item (Membership) Store a subset $S$ of size at most $s$ from a universe of size $n$ such that membership queries can be answered efficiently, i.e., decide if a given element from the universe is in $S$. \\ We construct an error-correcting data structure for this problem with length nearly linear in $s\log n$ that answers membership queries with $O(1)$ bit-probes. This nearly matches the asymptotically optimal parameters for the noiseless case: length $O(s\log n)$ and one bit-probe, due to Buhrman, Miltersen, Radhakrishnan, and Venkatesh. \item (Univariate polynomial evaluation) Store a univariate polynomial $g$ of degree $\deg(g)\leq s$ over the integers modulo $n$ such that evaluation queries can be answered efficiently, i.e., we can evaluate the output of $g$ on a given integer modulo $n$. \\ We construct an error-correcting data structure for this problem with length nearly linear in $s\log n$ that answers evaluation queries with $\polylog s\cdot\log^{1+o(1)}n$ bit-probes. This nearly matches the parameters of the best-known noiseless construction, due to Kedlaya and Umans. \end{itemize}
Cite as

Victor Chen, Elena Grigorescu, and Ronald de Wolf. Efficient and Error-Correcting Data Structures for Membership and Polynomial Evaluation. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 203-214, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.STACS.2010.2455,
  author =	{Chen, Victor and Grigorescu, Elena and de Wolf, Ronald},
  title =	{{Efficient and Error-Correcting Data Structures for Membership and Polynomial Evaluation}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{203--214},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2455},
  URN =		{urn:nbn:de:0030-drops-24558},
  doi =		{10.4230/LIPIcs.STACS.2010.2455},
  annote =	{Keywords: Data Structures, Error-Correcting Codes, Membership, Polynomial Evaluation}
}
Document
DOI: 10.4230/LIPIcs.STACS.2009.1813
Locally Decodable Quantum Codes

Authors: Jop Briet and Ronald de Wolf

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract
We study a quantum analogue of locally decodable error-correcting codes. A $q$-query \emph{locally decodable quantum code} encodes $n$ classical bits in an $m$-qubit state, in such a way that each of the encoded bits can be recovered with high probability by a measurement on at most $q$ qubits of the quantum code, even if a constant fraction of its qubits have been corrupted adversarially. We show that such a quantum code can be transformed into a \emph{classical} $q$-query locally decodable code of the same length that can be decoded well on average (albeit with smaller success probability and noise-tolerance). This shows, roughly speaking, that $q$-query quantum codes are not significantly better than $q$-query classical codes, at least for constant or small $q$.
Cite as

Jop Briet and Ronald de Wolf. Locally Decodable Quantum Codes. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 219-230, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{briet_et_al:LIPIcs.STACS.2009.1813,
  author =	{Briet, Jop and de Wolf, Ronald},
  title =	{{Locally Decodable Quantum Codes}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{219--230},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1813},
  URN =		{urn:nbn:de:0030-drops-18134},
  doi =		{10.4230/LIPIcs.STACS.2009.1813},
  annote =	{Keywords: Data structures, Locally decodable codes, Quantum computing}
}
Document
DOI: 10.4230/LIPIcs.STACS.2009.1802
Error-Correcting Data Structures

Authors: Ronald de Wolf

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract
We study data structures in the presence of adversarial noise. We want to encode a given object in a succinct data structure that enables us to efficiently answer specific queries about the object, even if the data structure has been corrupted by a constant fraction of errors. This new model is the common generalization of (static) data structures and locally decodable error-correcting codes. The main issue is the tradeoff between the space used by the data structure and the time (number of probes) needed to answer a query about the encoded object. We prove a number of upper and lower bounds on various natural error-correcting data structure problems. In particular, we show that the optimal length of error-correcting data structures for the {\sc Membership} problem (where we want to store subsets of size $s$ from a universe of size $n$) is closely related to the optimal length of locally decodable codes for $s$-bit strings.
Cite as

Ronald de Wolf. Error-Correcting Data Structures. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 313-324, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{dewolf:LIPIcs.STACS.2009.1802,
  author =	{de Wolf, Ronald},
  title =	{{Error-Correcting Data Structures}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{313--324},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1802},
  URN =		{urn:nbn:de:0030-drops-18024},
  doi =		{10.4230/LIPIcs.STACS.2009.1802},
  annote =	{Keywords: Data structures, Error-correcting codes, Locally decodable codes, Membership}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact